
//给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。 
//
// 
//
// 示例 1 : 
//
// 
//输入:nums = [1,1,1], k = 2
//输出: 2
//解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
// 
//
// 示例 2 : 
//
// 
//输入:nums = [1,2,3], k = 3
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 2 * 104 
// -1000 <= nums[i] <= 1000 
// 
// -107 <= k <= 107 
// 
// 
//
// 
//
// 注意：本题与主站 560 题相同： https://leetcode-cn.com/problems/subarray-sum-equals-k/ 
// Related Topics 数组 哈希表 前缀和 
// 👍 2 👎 0

package leetcode.editor.cn;
/**
  * 题目Id：剑指 Offer II 010
  * 题目：和为 k 的子数组
  * 日期：2021-08-24 09:55:23
*/
public class QTMn0o {
    public static void main(String[] args) {
        Solution solution = new QTMn0o().new Solution();
       System.out.println(solution.subarraySum(new int[]{1,1,1},2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        int count =0;
    public int subarraySum(int[] nums, int k) {
            dfs(0,0,nums,k);
     return count ;
    }

    public boolean dfs(int pre,int index,int nums[],int k){
        if (pre+nums[index]>k){
            //不必在寻找
            return false;
        }
        //如果相等 则表示找到
        if (pre+nums[index]==k||(index==0&&nums[index]==k)){
             count++;
             return true;
        }
        if (pre+nums[index]<k){
            pre=pre+nums[index];
            for (int i=index+1;i<nums.length;i++){
               if (!dfs(pre,i,nums,k)){
                   break;
               }
            }
            return true;
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}    
